package com.java.basis.sort;

/**
 * 排序算法-冒泡排序及算法优化 排序算法最好的事件是O(n),最坏的时间是O(n*n)
 * 
 * @author acer
 *
 */
public class BubbleSort2 {
	public static void main(String[] args) {
		int[] arr = { 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
//		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
//		System.out.println(arr);
		long t1 = System.currentTimeMillis();
		bubbleSortNormal(arr);// 调用常规版冒泡排序算法
//		bubbleSortOptimization1(arr);// 优化一
//		bubbleSortOptimization2(arr);// 优化二
		long t2 = System.currentTimeMillis();
		System.out.println("\n排序使用的时间t = " + (t2 - t1));

	}

	/**
	 * 冒泡排序常规版
	 * 
	 * @param arr
	 */
	public static void bubbleSortNormal(int[] arr) {
		// 从小到大
//		System.out.print("原始数据：");
//		for (int i : arr) {
//			System.out.print(i);
//		}
//		for (int i = 0; i < arr.length-1; i++) {
//			for (int j = 0; j < arr.length - 1 - i; j++) {
//				System.out.format("\n第 %d 遍：", i + 1);
//				if (arr[j + 1] < arr[j]) {
//					int temp = arr[j + 1];
//					arr[j + 1] = arr[j];
//					arr[j] = temp;
//				}
//				for (int m : arr) {
//					System.out.print(m);
//				}
//
//			}
//			System.out.println("");
//			for (int m : arr) {
//				System.out.print(m);
//			}
//		}

		// 从大到小
//		int temp = 0; // 开辟一个临时空间, 存放交换的中间值
		// 要遍历的次数
		for (int i = 0; i < arr.length - 1; i++) {
			System.out.format("第 %d 遍：\n", i + 1);
			// 依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
			for (int j = 0; j < arr.length - 1 - i; j++) {
				// 比较相邻的元素，如果前面的数小于后面的数，就交换
				if (arr[j] < arr[j + 1]) {
					int temp = arr[j + 1];
					arr[j + 1] = arr[j];
					arr[j] = temp;
				}
				System.out.format("第 %d 遍的第%d 次交换：", i + 1, j + 1);
				for (int count : arr) {
					System.out.print(count);
				}
				System.out.println("");
			}
			System.out.format("第 %d 遍最终结果：", i + 1);
			for (int count : arr) {
				System.out.print(count);
			}
			System.out.println("\n#########################");
		}

	}

	/**
	 * 冒泡排序优化一
	 * 针对已经排序结束，继续循环的问题
	 * 当数组是，5，4，3，1，2 的时候的时候就非常明显了，
	 * 实际上在第一次循环的时候整个数组就已经完成排序，但是常规版的算法仍然会继续后面的流程，这就是多余的了。
	 * 为了解决这个问题，我们可以设置一个标志位，用来表示当前第 i 趟是否有交换，如果有则要进行 i+1 趟，如果没有，则说明当前数组已经完成排序。
	 * @param arr
	 */
	public static void bubbleSortOptimization1(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int flag = 1; // 设置一个标志位
			// 依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
			for (int j = 0; j < arr.length - 1 - i; j++) {
				// 比较相邻的元素，如果前面的数小于后面的数，交换
				if (arr[j] < arr[j + 1]) {
					int temp = arr[j + 1];
					arr[j + 1] = arr[j];
					arr[j] = temp;
					flag = 0; // 发生交换，标志位置0
				}
			}
			System.out.format("第 %d 遍最终结果：", i + 1);
			for (int count : arr) {
				System.out.print(count);
			}
			System.out.println("");
			if (flag == 1) {// 如果没有交换过元素，则已经有序
				return;
			}

		}
	}

	/**
	 * 冒泡排序优化二
	 * 针对已经排序结束，继续循环的问题
	 * 在冒泡排序中还有一个问题存在，就是第 i 趟排的第 i 小或者大的元素已经在第 i 位上了，
	 * 甚至可能第 i-1 位也已经归位了，那么在内层循环的时候，有这种情况出现就会导致多余的比较出现。
	 * 例如：6，4，7，5，1，3，2，当我们进行第一次排序的时候，结果为6，7，5，4，3，2，1，实际上
	 * 后面有很多次交换比较都是多余的，因为没有产生交换操作。
	 * @param arr
	 */
	public static void bubbleSortOptimization2(int[] arr) {
		int len = arr.length - 1;
		int tempPostion = 0; // 记录最后一次交换的位置
		// 要遍历的次数
		for (int i = 0; i < arr.length - 1; i++) {
			int flag = 1; // 设置一个标志位
			// 依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
			for (int j = 0; j < len; j++) {
				// 比较相邻的元素，如果前面的数小于后面的数，交换
				if (arr[j] < arr[j + 1]) {
					int temp = arr[j + 1];
					arr[j + 1] = arr[j];
					arr[j] = temp;
					flag = 0; // 发生交换，标志位置0
					tempPostion = j; // 记录交换的位置
				}
				System.out.format("第 %d 遍第%d 趟结果：", i + 1, j + 1);
				for (int count : arr) {
					System.out.print(count);
				}
				System.out.println("");
			}
			len = tempPostion; // 把最后一次交换的位置给len，来缩减内循环的次数
			System.out.format("第 %d 遍最终结果：", i + 1);
			for (int count : arr) {
				System.out.print(count);
			}
			System.out.println("");
			if (flag == 1) {// 如果没有交换过元素，则已经有序
				return;
			}

		}

	}

}
